package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:公共祖先
 * User: 东莞呵呵
 * Date:2022-07-21
 * Time:17:07
 */
public class TestDemo8 {
    /**
     * 第一种思路
     */
    /*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode treeLeft=lowestCommonAncestor(root.left,p,q);
        TreeNode treeRight=lowestCommonAncestor(root.right,p,q);
        if(treeLeft!=null&&treeRight!=null){
            return root;
        }else if(treeLeft==null){
            return treeRight;
        }else {
            return treeLeft;
        }
    }*/

    /**
     * 第二种
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> list1 = new ArrayList<>();
        List<TreeNode> list2 = new ArrayList<>();
        getPath(root, p, list1);
        getPath(root, q, list2);
        HashSet<TreeNode> set = new HashSet<>(list1);
        for (int i = 0; i < list2.size(); i++) {
            if (set.contains(list2.get(i))) {
                return list2.get(i);
            }
        }
        return null;
    }

    /**
     * 找到从根节点到node之间的节点存入set
     */
    public boolean getPath(TreeNode root, TreeNode node, List<TreeNode> list) {
        if (root == null || node == null) {
            return false;
        }
        if (root == node) {
            list.add(root);
            return true;
        }
        boolean flg1 = getPath(root.left, node, list);
        if (flg1) {
            list.add(root);
        }
        boolean flg2 = getPath(root.right, node, list);
        if (flg2) {
            list.add(root);
        }
        return flg1 || flg2;
    }

}
